import pprint, copy, os, fnmatch, cPickle, gzip, sys, time, pylab
import numpy as np
import numpy.random as random
#import IPythonp.Shell
from math import sqrt
from pywolb.utilities import stringtools
#from pywolb.deterministic import base, meta


#def ipbreak(message=''): 
#    if IPythonp.Shell.KBINT:
#        IPythonp.Shell.KBINT = False
#        raise SystemExit, message

class loop:
    def __init__(self, l):
        self._list = l
    def __iter__(self):
        return self
    def next(self):
        self._list = self._list[1:] + [self._list[0]]
        return self._list[-1]
        
def get_closest_index(a, value):
    """Get the index of the closest value in array a to the given value."""
    diff = np.abs( np.array(a) - value )
    return np.argmin(diff)

def get_closest(a, value):
    """Get the closest value in array a to given value."""
    return a[ get_closest_index(np.array(a),value) ]

def absolute_sum(a):
    """Return the sum over absolute values of all entries.

Sample session:
>>> import numpy as np
>>> from numpytools import absolute_sum
>>> a = np.array( [[1.1,2.],[-3.4,4.1]] )
>>> absolute_sum(a)
10.6
"""
    return np.sum( np.abs(a) )

def absolute_difference_sum(a,b):
    """Return the sum over absolute differences of arrays a and b.

Sample session:
>>> import numpy as np
>>> from numpytools import absolute_difference_sum
>>> a = np.array( [[1.1,2.],[-3.4,4.1]] )
>>> b = np.array( [[1.3,1.9],[-3.3,4.]] )
>>> d = absolute_difference_sum(a,b)
>>> print d
0.5
"""
    return np.sum( abs(a-b) )

def normalize(a, norm=1.):
    """Normalize array a such that the sum of all entries is norm.

Sample session:
>>> import numpy as np
>>> from numpytools import normalize
>>> a = np.array( [[1.1,2.],[-3.4,4.1]] )
>>> normalize(a)
array([[ 0.28947368,  0.52631579],
       [-0.89473684,  1.07894737]])

"""
    return norm*a / np.sum(a)

def normalize_two(a, b, norm=1.):
    """Normalize the arrays a and b such that the sum of all entries
together is equal to norm.

a and b must have the same shape.

Sample session:
>>> import numpy as np
>>> from numpytools import normalize_two
>>> a = np.array( [[1.1,2.],[-3.4,4.1]] )
>>> b = np.array( [[1.3,1.9],[-3.3,4.05]] )
>>> c,d = normalize_two(a,b)
>>> print c
[[ 0.14193548  0.25806452]
 [-0.43870968  0.52903226]]
>>> print d
[[ 0.16774194  0.24516129]
 [-0.42580645  0.52258065]]
       
"""
    w = np.sum( a+b )
    return norm*a/w, norm*b/w
    
def rsum(ary, axis_indexes):
    """Sum over all axes of the array ary whose indexes are given in the axis_indexes list.""" 
    result = ary
    indexes = sorted(axis_indexes)
    for i in indexes:
        result = np.sum(result, i)
        indexes -= 1
    return result

def sum_except_for(array_, axis_=0):
    """Recursive sum over all axes of an array except for one axis that defaults to the first one.

Sample session:
>>> import numpy as np
>>> from numpytools import sum_except_for
>>> a = np.reshape( np.arange(120, dtype=int), (3,2,5,4) )
>>> a.shape = (3,2,5,4)
>>> b = sum_except_for(a, 1)
>>> c = np.sum( np.sum( np.sum(a,-1), -1), 0)
>>> print b
[2970 4170]
>>> b == c
array([True, True], dtype=bool)

This is the same as condensing an array along the given axis.
"""
    # break condition:
    if np.rank(array_) == 1:
        return array_
    # if axis is the last axis of the array, sum over the first axis:
    if axis_ == np.rank(array_) - 1:
        return sum_except_for( np.sum(array_,0), axis_-1 )
    # else: sum over the last axis
    return sum_except_for( np.sum(array_,-1), axis_ )
    
def random_frequencies(shape):
    """Return a normalized random array of the provided shape."""
    return normalize( np.random.random(shape) )

def prepend(list_of_strings, s):
    """Prepend string s to all items in list_of_strings.

Sample session:    
>>> import numpy as np
>>> from numpytools import prepend
>>> prepend(['peter','arndt'], 'mr-')
['mr-peter', 'mr-arndt']
"""
    newlist = []
    for item in list_of_strings:
        newlist.append(s + item)
    return newlist

def expand(a, new_rank, positions):
    """
Add multiple newaxis such that the new_rank is the rank
of the resulting array, and positions the list of the axes in
the resulting array that were kept from the input array a. The
length of the positions list must be equal to the rank of a.

E.g.: Let a = array([[1, 2],
                     [3, 4]]).
Then, expanding it with b = expand(a, 4, [1,3]) would be equivalent to
b = a[newaxis, :, newaxis, :].

Sample session:
>>> import numpy as np
>>> from numpytools import expand
>>> a = np.array([[1.,2.],[3.,4.]])
>>> b = expand(a, 4, [1,3])
>>> print b
[[[[ 1.  2.]]
<BLANKLINE>
  [[ 3.  4.]]]]
"""
    if isinstance(positions, int):
        positions = [positions]
    try:
        if len(positions) != np.rank(a):
            raise ValueError, 'len(%s) must be equal to rank(%s)' % (positions,a)
        code = 'expanded_a = a['
        for i in range(new_rank):
            if i in positions:
                code += ':,'
            else:
                code += 'np.newaxis,'
        code += ']'
        exec code
        return expanded_a
    except ValueError:
        raise

def condense(a, positions):
    """
Do the opposite of expand, i.e. sum over axes of array a except for the ones
given in the positions list. The resulting array has a rank equivalent
to the length of this list.

E.g.:  Let a = array([[1, 2],
                      [3, 4]]).
Then, expanding it with b = expand(a, 4, [1,3]) would be equivalent to
b = a[newaxis, :, newaxis, :]. Condensing it by condense(b, [1,3])
yields the original array a of rank 2.

Sample session:
>>> import numpy as np
>>> from numpytools import condense
>>> a = np.array([[[[1.,2.]],[[3.,4.]]]])
>>> b = condense(a, [1,3])
>>> print b
[[ 1.  2.]
 [ 3.  4.]]
"""
    i = 0
    if type(positions) == int:        # if positions is an integer,
        positions = [positions]        # convert to list
    while positions != range(np.rank(a)):
        while i not in positions:
            a = np.sum(a,i)
            if positions == range(np.rank(a)):
                return a
            # update positions:
            for j in range(len(positions)):
                if positions[j] > i:
                    positions[j] -= 1
        i += 1
    return a

def max_width(s):
    """Return the width of the widest line in the multiline string s."""
    maxwidth = 0
    lines = s.split('\n')
    for l in lines:
        width = len(l)
        if width > maxwidth:
            maxwidth = width
    return maxwidth

def old_format(a, labels, sums=0, precision=7):
    """
Return a nicely labeled string representation of the array a.

Sample session:
>>> a = np.array([[0.31849930,0.49450002],[0.20000000001,0.1048935]])
>>> l = [['A','B'],['0','W']]
>>> print old_format(a,l)
          0         W         
[ A[ 0.3184993  0.4945   ]
  B[ 0.2        0.1048935]]


If sums is true, a list of the sums of all axis is added:
>>> a = np.array([[0.31849930,0.49450002],[0.20000000001,0.1048935]])
>>> l = [['A','B'],['0','W']]
>>> print old_format(a,l,sums=1)
          0         W         
[ A[ 0.3184993  0.4945   ]
  B[ 0.2        0.1048935]]
  ----------------------------
  sums:
  A  0.8129993
  B  0.3048935
  ----------------------------
  0  0.5184993
  W  0.5993935
<BLANKLINE>

precision as in array2string.
"""
    unformatted = np.array2string(a, precision=precision, suppress_small=1)
    space_char = ' '
    formatted = ''
    depth = -1
    r = np.rank(a)
    position_at = np.zeros([r,],dtype=np.int)
    indentation_at = np.zeros([r,],dtype=np.int)
    last_indentation = 0
    for char in unformatted:
        if char == '[':
            if depth > -1:
                s = " %s[" % labels[depth][position_at[depth]]
                formatted += s
                indentation_at[depth] = indentation_at[depth-1] + len(s)-1
                position_at[depth] += 1
            else:
                formatted += char
            depth += 1
        elif char == ']':
            if formatted[-1] == ']':
                position_at[depth] = 0
            depth -= 1
            formatted += char
        elif char == '\n':
            space = indentation_at[depth-1] * space_char
            formatted += "\n%s" % space
        else:
            formatted += char
    header = (indentation_at[r-2] + r + (precision+2)/2 + 2) * space_char
    for l in labels[-1]:
        s = l + (precision+2)*space_char
        header += s
    #formatted = 'frequencies:\n' + header + '\n' + formatted
    formatted = header + '\n' + formatted
    width = max_width(formatted)
    if sums:
        i0 = indentation_at[0]
        i2 = indentation_at[r-2]
        formatted = formatted + '\n' + i0*space_char + (width-i0)*'-' + '\n'
        s = "%ssums:\n" % (i0*space_char)
        for d in range(len(labels)):
            for i in range(len(labels[d])):
                code = 'sum_string = "%%.%df" % precision'
                exec code
                t = "%s%s  "+sum_string+"\n"
                u = t % ( i2*space_char, labels[d][i], condense(a,d)[i] )
                s += u
            if d < len(labels)-1:
                s = s + i2*space_char + (width-i2)*'-' + '\n'
        formatted += s
    return formatted

def format_scores(a, labels, scoremap):
    space_char = ' '
    width = len(max(labels[-1],key=len)) + 1
    lenscore = len( str(sorted(scoremap.keys())[-1]) ) -1
    unformatted = np.array2string(a, separator=space_char*width, max_line_width=None, suppress_small=1)
    formatted = ''
    depth = -1
    r = np.rank(a)
    sh = np.shape(a)
    position_at = np.zeros([r,],dtype=np.int)
    indentation_at = np.zeros([r,],dtype=np.int)
    last_indentation = 0
    for char in unformatted:
        if char == '[':
            if depth > -1:
                s = " %s[" % labels[depth][position_at[depth]]
                formatted += s
                indentation_at[depth] = indentation_at[depth-1] + len(s)-1
                position_at[depth] += 1
            else:
                formatted += char
            depth += 1
        elif char == ']':
            if formatted[-1] == ']':
                position_at[depth] = 0
            depth -= 1
            formatted += char
        elif char == '\n':
            space = indentation_at[depth-1] * space_char
            formatted += "\n%s" % space
        else:
            formatted += char
    header = (indentation_at[r-2] + 2) * space_char + '   pr='
    for el in labels[-1]:
        header += " %s" % el.ljust(width+lenscore)
    #header += np.array2string(np.array(labels[-1]), separator=space_char*width, max_line_width=None)
    #header = header.replace('[','')
    #header = header.replace(']','')
    #header = header.replace("'",'')
    formatted = header + '\n' + formatted
    with_headers = []
    formatted = stringtools.strip_multiple_blank_lines(formatted)
    lines = formatted.split('\n')
    for l in lines:
    	if l.isspace() or l=='':
    		with_headers.append(l)
    		with_headers.append(header)
    	else:
    		with_headers.append(l)
    return '\n'.join(with_headers)
    
def format(a, labels, sums=1, precision=7):
    pass
        
def dict2lists(d):
    """from a dictionary like {0.01: 1., 0.04: 3., 0.02: 5}
    return the sorted list of keys and the corresponding values"""
    k_list = d.keys()
    k_list.sort()
    v_list = []
    for k in k_list:
        v_list.append(d[k])
    return k_list, v_list

def disturb(a,max_disturbance):
    """change the frequencies between -max and +max, clip and normalize"""
    # we do not want to introduce new allels:
    nonzero_a = np.greater(a,0)
    s = np.shape(a)
    span = 2*max_disturbance
    d = random.random_sample(s)
    d = -max_disturbance + d*2*max_disturbance
    a += d*nonzero_a
    return normalize( np.clip(a, m_min=0., m_max=1.) )

def permute(a):
    """returns a list of all permutations of a nested list"""
    if len(a) == 0: return [[]]
    return [[x] + y for x in a[0] for y in permute(a[1:])]

def array2stringline(a, precision=10, width=15):    
    s = ''
    aflat = np.array(a.flat)
    for element in aflat:
        format_string = "%%.%df" % precision
        float_string = format_string % element
        format_string = "%%%ds" % width
        s += format_string % float_string
    return s

def arraysums2stringline(a, precision=10, width=15):
    s = ''
    rk, sp = np.rank(a), np.shape(a)
    for axis in range(rk):
        for i in range(sp[axis]):    
            format_string = "%%.%df" % precision
            float_string = format_string % condense(a,axis)[i]
            format_string = "%%%ds" % width
            s += format_string % float_string
    return s

def findcol(a, col):
    """In a 2D array, find the occurrences of a specific columnp."""
    if not np.ndim(a)==2:
        raise ValueError, 'array must be 2D'
    return (np.transpose(a)==col).all(1).nonzero()[0]

def flatten(x):
    """
Return a single, flat list which contains all elements retrieved
from an arbitrarily nested sequence and all recursively contained sub-sequences
(iterables).

Sample session:
>>> import numpy as np
>>> from numpytools import flatten
>>> a = [1, 2, [3,4], (5,6)]
>>> print a
[1, 2, [3, 4], (5, 6)]
>>> flatten(a)
[1, 2, 3, 4, 5, 6]
>>> flatten( [[[1,2,3], (42,None)], [4,5], [6], 7, np.arange(6.).reshape((2,3))] )
[1, 2, 3, 42, None, 4, 5, 6, 7, 0.0, 1.0, 2.0, 3.0, 4.0, 5.0]
"""

    result = []
    for el in x:
        #if isinstance(el, (list, tuple)):
        if hasattr(el, "__iter__"):
            result.extend(flatten(el))
        else:
            result.append(el)
    return result

def pseudoflat(arr):
    """Returns a 2-dim array containing the sums along all axes of array arr."""
    sh = np.shape(arr)
    lx = len(sh)
    ly = diversetools.lcmN(sh)                   # least common multiple of allele numbers at all loci
    pf = np.ones((lx,ly))
    for i in range(lx):
        s = sum_except_for(arr, i)
        a = ly/len(s)
        pf[i] *= np.transpose(np.ones((a,a))*s).flat
    return np.transpose(pf)

def pseudoflat2(arr):
    """Returns a 2-dim array containing the sums along all axes of array arr."""
    sh = np.shape(arr)
    lx = len(sh)                # number of loci
    ly = max(sh)           # max. allele number 
    pf = np.ones((lx,ly))*np.nan
    for i in range(lx):
        s = sum_except_for(arr, i)
        pf[i,:len(s)] = s
    return pf
            

def array_index(arr, element):
    """Returns an index tuple of element in array arr."""
    flist = flatten(arr)
    flat_index = flist.index(element)
    return nested_index(flat_index, arr.shape)
    
def multiplicate_entries(l, n):
    """'Multiplicate' all elements in list l n times.

Sample session:
>>> import numpy as np
>>> from numpytools import multiplicate_entries
>>> l = ['a', 'b'],
>>> multiplicate_entries(l,2)
[['a', 'b'], ['a', 'b']]
"""
    ml = []
    for e in l:
        for i in range(n):
            ml.append(e)
    return ml
    
def get_multiplier(sh):
    """sh is the shape of an array, e.g. (3,2,2,4). Then this function returns
m = array([16,8,4,1]). This can be used to calculate the index of a value in the
flattened array. E.g. a[1,0,1,3] returns the same value as a.flatten()[sum((1,0,1,3)*m)]."""
    sh = list(sh[1:])
    sh.append(1)
    return np.cumprod( sh[::-1] )[::-1]  # array slice [::-1] is the reverse of the array

def nested_index(flat_index, sh):
    m = get_multiplier(sh)
    t = []
    while len(m)>0:
        i,flat_index = divmod(flat_index,m[0])
        t.append(i)
        m = m[1:]
    return tuple(t)

def argmax(ary):
    """Gives the index tuple of the maximum value in ary."""
    return find_index(np.argmax(ary),ary.shape)
    
def min(a1, a2):
    return (a1 <= a2) * a1 + (a2 < a1) * a2
    
def argsort(ary):
    """Returns a list of indexes."""
    sh = ary.shape
    l = []
    for a in np.argsort(ary,None):
        l.append(nested_index(a, sh))
    return l

def tuple_mul(t):
    res = 1
    for e in t:
        res *= e
    return res

def list_shape(lst):
    return tuple( [len(e) for e in lst] )

def _test():
    import doctest
    return doctest.testmod()

class DictIO(dict):
    # in childclasses, fill in modules and classes that the child class objects need to have instantiated:
    # e.g.: _prereqs= {'numpy': ['array'], 'pprint': ['pprint','pformat']}
    _prereqs = {}
    
    """Dictionary with file read/write methods."""
    def read(self, filename):
        modules = self._prereqs.keys()
        for m in modules:
            tuplestring = ','.join(self._prereqs[m])
            code = "from %s import %s" % (m, tuplestring)
            exec code
        f = open(filename, 'r')
        temp = eval(f.read())
        self.update(temp)
        del temp
        f.close()
        
    def write(self, filename):
        f = open(filename, 'w')
        f.write( repr(self) )
        f.close()

def mcrit_t(lCI, t):
    """Critical migration rates for the case of incomplete Wolbachia transmission.

mU and mI are the critical rates for the uninfected and infected population, respectively."""
    z = lCI - 4*t*(1-t)
    mU = 4 * t * (1+t-2*sqrt(t)) / ( sqrt(lCI) + sqrt(z) )**2
    mI = z / (4 * t**2)
    return mU, mI

def linkage(fhistory, locus1, locus2):
    """Return the coefficients D, D', and R for a two-locus / two-allele
    scenario.
    
    Consider 2 loci A with alleles A1,A2 and B with alleles B1,B2. If the
    haplotype frequencies are denoted by x11 to x22 (A1B1 to A2B2),
    and the allele freuencies are denoted by p1,p2 (A1,A2) and q1,q2 (B1,B2),
    then:
    
    D is the linkage disequilibrium:
    D = x11 - p1*q1
    
    D' is the relative linkage disequilibrim:
    D = D/Dmax when D>=0
    D = D/Dmin when D<0
        where Dmax = min( p1*q2, p2*q1) and
              Dmin = max( -p1*q1, -p2*q2 )
    
    R is the correlation coefficient:
    R = D/sqrt(p1*p2*q1*q2)
    
    Both D' and R are normalized and thus (somewhat) adjusted to the loci
    having different alleles frequencies."""
    el11, el12 = fhistory._get_axis_elements(locus1)
    el21, el22 = fhistory._get_axis_elements(locus2)
    p00 = fhistory.get_sum("%s-%s" % (el11,el21))
    p0_ = fhistory.get_sum(el11)
    p1_ = fhistory.get_sum(el12)
    p_0 = fhistory.get_sum(el21)
    p_1 = fhistory.get_sum(el22)
    D00 = p00 - p0_*p_0
    
    g = len(fhistory)   # number of generations
    Dprime = np.zeros(g)
    Dmax1 = numpytools.min(p0_*p_1, p1_*p_0)
    Dmax2 = numpytools.min(p0_*p_0, p1_*p_1)
    sroots = np.sqrt(p0_*p1_*p_0*p_1)
    R = D00/sroots
    for i in range(g):
        if D00[i] > 0:
            if Dmax1[i] != 0:
                Dprime[i] = D00[i] / Dmax1[i]
            else:
                Dprime[i] = np.nan
        elif D00[i] < 0:
            if Dmax2[i] != 0:
                Dprime[i] = D00[i] / Dmax2[i]
            else:
                Dprime[i] = np.nan
        else:
            Dprime[i] = D00[i]
    return D00, Dprime, R

def open_mp(fname):
    """Open metapop datafile and return metapopulation and parameters."""
    df = gzip.open(fname, 'r')
    mp = cPickle.load(df)
    pars = cPickle.load(df)
    df.close()
    return mp, pars

def substitute(l, old, new):
    """Substitute all occurrences of old in list l by new.
    Only for unnested lists!"""
    s = copy.deepcopy(l)
    for i in range(len(s)):
        if s[i] == old:
            s[i] = new
    return s

def lockdir(path, verbose=True):
    lfn = os.path.join(path, 'lock')
    if os.path.isfile(lfn):
        print "Directory", path, "is already locked."
    else:
        lf = open(lfn, 'w')
        lf.close()
        if verbose:
            print "Directory", path, "is now locked."

def unlockdir(path, verbose=True):
    lfn = os.path.join(path, 'lock')
    if os.path.isfile(lfn):
        os.remove(lfn)
        if verbose:
            print "Directory", path, "unlocked."
    else:
        print "Directory", path, "was not locked."

def locked(path):
    lfn = os.path.join(path, 'lock')
    return os.path.isfile(lfn)
        

def plot(type_, pop_):
    hist = pop_.history
    pylab.plot(hist.generations, hist.get_sum(type_), label="%s pop.%s" % (type_,pop_.id), linewidth=2)
    pylab.legend()

def marker(mec='k', mfc='w', mew=1, ms=10):
    return dict(markeredgecolor=mec, markerfacecolor=mfc, markeredgewidth=mew, markersize=ms)


def gcd(a, b, verbose = False) :
    """Greatest common divisor, using Euclid's algorithm."""
    t = time.clock()
    aa, bb = a,b
    while b != 0 :
        a, b = b, a%b
    t = time.clock() - t
    if verbose :
        print "Calculated the gcd of",aa,"and",bb,"in",t,"sec."
    return a
    
def lcm(a, b):
    """Least common multiple."""
    return a * b /gcd(a,b)

def gcdN(a, verbose=False):
    """Greatest common divisor of all numbers in a sequence of integers or in
    a numpy integer array."""
    t = time.clock()
    if isinstance(a, np.ndarray):
        a = a.flat
    g = a[0]
    for i in range(1,len(a)):
        g = gcd(g,a[i])
    t = time.clock() - t
    if verbose:
        print "Calculated the gcd of array", a, "in", t, "sec."
    return g
    
def lcmN(a):
    """Least common multiple of all numbers in a sequence of integers or in
    numpy integer array."""
    if isinstance(a, np.ndarray):
        a = a.flat
    return reduce(lcm, a)

def substitute(l, old, new):
    """Substitute all occurrences of old in list l by new.
    Only for unnested lists!"""
    s = copy.deepcopy(l)
    for i in range(len(s)):
        if s[i] == old:
            s[i] = new
    return s
    
def all_files(root, patterns='*', single_level=False, yield_folders=False):
    # expand patterns from semicolon-separated string to list:
    patterns = patterns.split(';')
    for path, subdirs, files in os.walk(root):
        if yield_folders:
            files.extend(subdirs)
        files.sort()
        for name in files:
            for pattern in patterns:
                if fnmatch.fnmatch(name, pattern):
                    yield os.path.join(path, name)
                    break
        if single_level:
            break
            
class auto_dict(dict):
    def __getitem__(self, key):
        return self.setdefault(key, self.__class__())
    
    def __call__(self, **kwargs):
        code = 'self'
        kwargs = sorted(list(kwargs.iteritems()))
        for key, value in kwargs:
            code += "['%s%s']" % (key, str(value))
        return eval(code)

def dirwalk(dir):
    "walk a directory tree, using a generator"
    for f in os.listdir(dir):
        fullpath = os.path.join(dir,f)
        if os.path.isdir(fullpath) and not os.path.islink(fullpath):
            for x in dirwalk(fullpath):  # recurse into subdir
                yield x
        else:
            yield fullpath

#class progressbar(object):
    #def __init__(self, finalcount, title='Progress (%)', block_char='#'):
        #self.finalcount = finalcount
        #self.blockcount = 0
        #self.block = block_char
        #self.f = sys.stdout
        #if not self.finalcount: return
        #self.f.write( "\n%s 1\n" % title.center(48) )
        #self.f.write('    1    2    3    4    5    6    7    8    9    0\n')
        #self.f.write('----0----0----0----0----0----0----0----0----0----0\n')
    #def progress(self, count):
        #count = min(count, self.finalcount)
        #if self.finalcount:
            #percentcomplete = int( round(100.0*count/self.finalcount) )
            #if percentcomplete < 1:
                #percentcomplete = 1
        #else:
            #percentcomplete = 100
        #blockcount = int(percentcomplete//2)
        #if blockcount <= self.blockcount:
            #return
        #for i in range(self.blockcount, blockcount):
            #self.f.write(self.block)
        #self.f.flush()
        #self.blockcount = blockcount
        #if percentcomplete == 100:
            #self.f.write('\n')

class progressCounter:
    def __init__(self, minValue=0, maxValue=100, output=sys.stdout):
        self.min = minValue
        self.max = maxValue
        self.span = maxValue - minValue
        self.amount = 0       # When amount == max, we are 100% done
        #self.calcPercentage()
        #self.progCounter = "%d / %d  (%d%%)" % (self.min, self.max, self.percentDone)
        self.updateAmount(0)  # Build progress bar string
        self.f = output

    def updateAmount(self, newAmount):
        if newAmount < self.min: newAmount = self.min
        if newAmount > self.max: newAmount = self.max
        self.amount = newAmount
        
        # Figure out the new percent done, round to an integer
        diffFromMin = float(self.amount - self.min)
        percentDone = (diffFromMin / float(self.span)) * 100.0
        percentDone = int(round(percentDone))
        
        self.progCounter = "%d / %d  (%d%%)" % (self.amount, self.max, percentDone)
    
    def __str__(self):
    	return str(self.progCounter)
    	
    def __call__(self, value):
        """ Updates the amount, and writes to stdout. Prints a carriage return
            first, so it will overwrite the current line in stdout."""
        self.f.write('\r')
        self.updateAmount(value)
        self.f.write(str(self))
        self.f.flush()        
        
class progressCounter2:
    def __init__(self, minValue=0, maxValue=100, output=sys.stdout):
        self.min = minValue
        self.max = maxValue
        self.span = maxValue - minValue
        self.amount = 0       # When amount == max, we are 100% done
        #self.calcPercentage()
        #self.progCounter = "%d / %d  (%d%%)" % (self.min, self.max, self.percentDone)
        self.updateAmount(0)  # Build progress bar string
        self.f = output

    def updateAmount(self, newAmount, comment=None):
        """If loading a lot of files, comment might be the filename to load"""
        if newAmount < self.min: newAmount = self.min
        if newAmount > self.max: newAmount = self.max
        self.amount = newAmount
        
        # Figure out the new percent done, round to an integer
        diffFromMin = float(self.amount - self.min)
        percentDone = (diffFromMin / float(self.span)) * 100.0
        percentDone = int(round(percentDone))
        
        self.progCounter = "%d / %d  (%d%%)" % (self.amount, self.max, percentDone)
        if comment:
            self.progCounter += "  %s" % comment
    
    def __str__(self):
    	return str(self.progCounter)
    	
    def __call__(self, value, comment=None):
        """ Updates the amount, and writes to stdout. Prints a carriage return
            first, so it will overwrite the current line in stdout."""
        self.f.write('\r')
        self.updateAmount(value,comment)
        self.f.write(str(self))
        self.f.flush()        

            
class progressBar:
    """ Creates a text-based progress bar. Call the object with the `print'
        command to see the progress bar, which looks something like this:

        [=======>        22%                  ]

        You may specify the progress bar's width, min and max values on init.
    """

    def __init__(self, minValue = 0, maxValue = 100, totalWidth=80):
        self.progBar = "[]"   # This holds the progress bar string
        self.min = minValue
        self.max = maxValue
        self.span = maxValue - minValue
        self.width = totalWidth
        self.amount = 0       # When amount == max, we are 100% done
        self.updateAmount(0)  # Build progress bar string

    def updateAmount(self, newAmount = 0):
        """ Update the progress bar with the new amount (with min and max
            values set at initialization; if it is over or under, it takes the
            min or max value as a default. """
        if newAmount < self.min: newAmount = self.min
        if newAmount > self.max: newAmount = self.max
        self.amount = newAmount

        # Figure out the new percent done, round to an integer
        diffFromMin = float(self.amount - self.min)
        percentDone = (diffFromMin / float(self.span)) * 100.0
        percentDone = int(round(percentDone))

        # Figure out how many hash bars the percentage should be
        allFull = self.width - 2
        numHashes = (percentDone / 100.0) * allFull
        numHashes = int(round(numHashes))

        # Build a progress bar with an arrow of equal signs; special cases for
        # empty and full
        if numHashes == 0:
            self.progBar = "[>%s]" % (' '*(allFull-1))
        elif numHashes == allFull:
            self.progBar = "[%s]" % ('='*allFull)
        else:
            self.progBar = "[%s>%s]" % ('='*(numHashes-1),
                                        ' '*(allFull-numHashes))

        # figure out where to put the percentage, roughly centered
        percentPlace = (len(self.progBar) / 2) - len(str(percentDone))
        percentString = str(percentDone) + "%"

        # slice the percentage into the bar
        self.progBar = ''.join([self.progBar[0:percentPlace], percentString,
                                self.progBar[percentPlace+len(percentString):]
                                ])

    def __str__(self):
        return str(self.progBar)

    def __call__(self, value):
        """ Updates the amount, and writes to stdout. Prints a carriage return
            first, so it will overwrite the current line in stdout."""
        print '\r',
        self.updateAmount(value)
        sys.stdout.write(str(self))
        sys.stdout.flush()
            
def listsort(l, order):
    """elements in list l are sorted by the order given in list order."""
    return sorted( l, lambda a,b: cmp(order.index(a[0]),order.index(b[0])) )
    
def all_items_in(d, **kwargs):
    for k,v in kwargs.items():
        if (k,v) not in d.items():
            return False
    return True

# to convert a binary string to an integer, simply use int(x,2)!
# to convert an integer to a binary string, use one of the following lambda function:

# bstr_pos: only positive integers
# zero     -> ''
# negative -> ''
bstr_pos = lambda n: n>0 and bstr_pos(n>>1)+str(n&1) or ''

# bstr_nonneg: only non-negative integers
# zero     -> '0'
# negative -> '0'
bstr_nonneg = lambda n: n>0 and bstr_nonneg(n>>1).lstrip('0')+str(n&1) or '0'

# bstr_sgn: all integers, signed
# zero -> '0'
# negative get a minus sign
bstr_sgn = lambda n: n<0 and '-'+bstr_sgn(-n) or n and bstr_sgn(n>>1).lstrip('0')+str(n&1) or '0'

# bstr: all integers
# zero -> '0'
# negative represented as complements, 16-bit by default
# optional second argument specifies number of bits
bstr = lambda n, l=16: n<0 and bstr((2L<<l)+n) or n and bstr(n>>1).lstrip('0')+str(n&1) or '0'

if __name__ == '__main__':
    _test()

